package com.zjj.algorithm.learning.dmsxl.tree;

/**
 * 101. 对称二叉树
 * 简单题
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 * <p>
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 * <p>
 * <p>
 * 提示：
 * <p>
 * 树中节点数目在范围 [1, 1000] 内
 * -100 <= Node.val <= 100
 *
 * @author zjj_admin
 * @date 2022/12/26 9:50
 */
public class Tree_08_SymmetricTree {

    public static void main(String[] args) {

        /**
         *          1
         *      2       2
         *   3    4   4    3
         *     5          5
         */


        TreeNode node1 = new TreeNode(1);
        TreeNode node2_1 = new TreeNode(2);
        TreeNode node2_2 = new TreeNode(2);
        TreeNode node3_1 = new TreeNode(3);
        TreeNode node3_2 = new TreeNode(3);
        TreeNode node4_1 = new TreeNode(4);
        TreeNode node4_2 = new TreeNode(4);
        TreeNode node5_1 = new TreeNode(5);
        TreeNode node5_2 = new TreeNode(5);

        node1.left = node2_1;
        node1.right = node2_2;
        node2_1.left = node3_1;
        node2_1.right = node4_1;
        node2_2.left = node4_2;
        node2_2.right = node3_2;
        node3_1.right = node5_1;
        node3_2.left = node5_2;
        boolean res = isSymmetric(node1);
        System.out.println("res = " + res);
    }


    /**
     * 思路，可以采用递归或者迭代的方式解答
     * 递归：比较根节点的左右孩子节点是否相同，然后递归遍历左孩子节点左节点和右孩子的右节点等等是否相同
     *
     * @param root
     * @return
     */
    public static boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);


    }

    /**
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 39.6 MB
     * 击败
     * 70.52%
     *
     * @param left
     * @param right
     * @return
     */
    private static boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right != null) {
            return false;
        }
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) {
            return false;
        }
        boolean compareOutSide = compare(left.left, right.right);
        boolean compareInSide = compare(left.right, right.left);
        return compareOutSide && compareInSide;
    }

}
